/*
 * triangulation.hpp
 *
 *  Created on: 16/11/2011
 *      Author: Aeradon
 */

#ifndef TRIANGULATION_HPP_
#define TRIANGULATION_HPP_

#include <list>
#include <vector>

#include "../include/point.hpp"

class Constraint;
class SymEdge;
class Vertex;
class Face;
class Edge;

//#ifdef _BUILD_DLL
//   #define DLLDIR  __declspec(dllexport)   // export DLL information
//#else
//   #define DLLDIR  __declspec(dllimport)   // import DLL information
//#endif
//
//class DLLDIR Triangulation
class Triangulation
{

public: // DEFINITIONS
	typedef float	   T;

	// enums for return values;
	enum P_LOCAL
	{
		P_LOCAL_NOTFOUND,
		P_LOCAL_TRIANGLE,
		P_LOCAL_EDGE,
		P_LOCAL_VERTEX
	};

	static constexpr float EPSILON = 0.00001;

public:
	Triangulation(float w, float h);
	virtual ~Triangulation();

	//insert point v1=(x1,y1) and v2 = (x2,y2) then invoke insertLineConstraint()
	void insertConstraint( T x1, T y1, T x2, T y2, unsigned int id );
	void insertConstraint(Constraint constraint);

	//insert constrained line segments with endpoints v1 and v2
	//it invokes insertLineConstraintSimple in the common case
	void insertLineConstraint(Vertex* v1, Vertex* v2, Constraint* c);
	void insertLineConstraintSimple(Vertex* v1, Vertex* v2, Constraint* c, Vertex* left, Vertex* right);

	// tries to insert vertex (x,y). return existing vertex if insertion overlaps
	Vertex* findOrInsertVertex(T& x, T& y);

	//constrained Delaunay point insertion within a face
	Vertex* insertPointInFace(Face* f, T& x,T& y);

	//constrained Delaunay point insertion on an edge
	Vertex* insertPointOnEdge(SymEdge* e, T& x,T& y);
	//constrained Delaunay point insertion on an edge.
	//left and right endpoint of the splitting constraint is reset.
	Vertex* insertPointOnEdge(SymEdge* e, T& x, T& y,Vertex* left,Vertex* right);

	//restore constrained Delaunay property using edge flip procedure
	void legalizedEdge(SymEdge* e);
	void legalizeEdge(SymEdge* e, int* entryVextexIndex);
	bool isLegalEdge(SymEdge* e);

	bool isConnected(Vertex* v1Itr, Vertex* v2Itr, SymEdge** eItr);
	bool isConnected(Vertex* v1Itr, Vertex* v2Itr);

	//edge flip operation on quadrilateral with diagonal edge e
	SymEdge* flip(SymEdge* e);

	//retriangulate the open region form by constraint insertion.
	void triangulatePseudoPolygon(std::list<Vertex*>& l_vertex, SymEdge* e);

	// Locate Point
	P_LOCAL locatePointLinear(
			T& x,
			T& y,
			Face** resultFace,
			SymEdge** resultEdge,
			Vertex** resultVertex);

	Face* locatePointInFace(T& x,T& y, Face* faceStart = nullptr);

	P_LOCAL locatePoint(
			T& x,
			T& y,
			Face** resultFace,
			SymEdge** resultEdge,
			Vertex** resultVertex);

	P_LOCAL locatePoint(Face* iniface,
			SymEdge* dummy,
			T& x, T& y,
			Face** resultFace,
			SymEdge** resultEdge,
			Vertex** resultVertex,
			int& visited);

	Face*   locateStartTriangle(Vertex* v1, Vertex* v2);

	bool onVertex(Face* f, T& x, T& y, Vertex** resultVertex);
	bool onEdge(Face* f, T& x, T& y, SymEdge** resultEdge);

	bool hasCoincidentSegments(Vertex* v1, Vertex* v2, SymEdge** coincidentEdge);

	/*bool findCrossEdges(Vertex* v1, Vertex* v2,
			std::list<Vertex*>& pu,
			std::list<Vertex*>& pm,
			std::list<Vertex*>& pl,
			std::list<SymEdge*>& ul,
			Vertex* left, Vertex* right);*/

	void findCrossEdgesLinear(Vertex* v1, Vertex* v2, std::list<Edge*> &l_edge);

	void findConstrainedCrossEdges(Vertex* v1, Vertex* v2,
			std::list<std::pair<int,SymEdge*> >& cl,
			std::vector<Vertex*>& pm);

	void findConstrainedCrossEdgesLinear(Vertex* v1, Vertex* v2,
			std::list<std::pair<int,SymEdge*> >& cl,
			std::vector<Vertex*>& pm);

	//perform straight-line walk on triangls cut by line segment v1-v2
	//store intersecting unconstrained line segments in ul
	void findUnconstrainedCrossEdges(Vertex* v1, Vertex* v2,
								   std::list<Vertex*>& pu,
								   std::list<Vertex*>& pl,
								   std::list<SymEdge*>& ul,
								   Vertex* /*left*/, Vertex* right);

	void findUnconstrainedCrossEdgesLinear(Vertex* v1, Vertex* v2,
			std::list<Vertex*>& pu,
			std::list<Vertex*>& pl,
			std::list<SymEdge*>& ul,
			Vertex* /*left*/, Vertex* right);


public: // Math Operations
	// Calculate if the triangle formed by the poins is CW, CCW or colinear
	static int  ccw(Vertex* v_a, Vertex* v_b, Vertex* v_c);
	static int  ccw(Point<float> p_a, Point<float> p_b, Point<float> p_c);
	static int  ccw(T x1, T y1, T x2, T y2, T x3, T y3);

	static T sign(T x1, T y1, T x2, T y2, T x3, T y3);

	static bool isPointInTri(T x, T y, Face* face);

	static bool overlap(T& x1, T& y1, T& x2, T& y2);

	static bool onSegment(T& x1, T& y1, T& x2, T& y2, T& x, T& y);

	static bool insideArea(T& x1, T& y1, T& x2, T& y2, T& x, T& y);

	static int  inCircle(T& p1x, T& p1y, T& p2x, T& p2y, T& p3x, T& p3y, T& px,  T& py);

	static bool segments_intersect(T& x1, T& y1, T& x2, T& y2, T& x3, T& y3, T& x4, T& y4);

	static bool findIntersect(T& x1, T& y1,T& x2, T& y2, T& x3, T& y3, T& x4, T& y4, T& vx, T& vy);
	static bool findIntersectParam(T x1, T y1, T x2, T y2, T x3, T y3, T x4, T y4, T &vx, T &vy);

public:	// operators

	Vertex* createVertex(T x, T y);
	Edge* createEdge(Vertex* v1, Vertex* v2);
	SymEdge* createSymEdge(Vertex* v1, Vertex* v2);
	Face* createFace(SymEdge* e1, SymEdge* e2, SymEdge* e3);
	Face* createFace(std::vector<SymEdge*>& edges);

	SymEdge* resetSymEdge(SymEdge* e, Vertex* v1, Vertex* v2);

	void removeFace(Face* f);
	void removeEdge(Edge* e);
	void removeSymEdge(SymEdge* e);
	void removeVertex(Vertex* v);
	// XXX void removeConstraint(Constraint* c);

	SymEdge* splitFace(Face* f, Vertex* v1, Vertex* v2);
	Face* joinFaces(Face* f1, Face* f2, SymEdge* e);
	void splitAndLinkEdge(SymEdge* e1, Vertex* v5);
	void splitAndLinkEdge(SymEdge* e1, Vertex* v5, Vertex* left, Vertex* right);

	void addConstraint(SymEdge* e, Constraint* c, Vertex* left, Vertex* right);

	Face* getOpposedFace(Face* f, Vertex* v, SymEdge** shareEdge);

	static bool vertexAboveSegment(Vertex* v1,Vertex* v2, Vertex* v);
	static bool vertexBelowSegment(Vertex* v1,Vertex* v2, Vertex* v);

	inline Point<float> getWH() const { return Point<float>(width, height); }
	inline std::vector<Face*>& getVFace()    { return v_face;    };
	inline std::vector<Edge*>& getVEdge()    { return v_edge;    };
	inline std::vector<SymEdge*>& getVSymEdge() { return v_symEdge; };

#ifdef _DEBUG
	void printTriangulation();
	void printSymEdgeList();
	void printRenderQueue(int x, int y);
#endif

#ifdef PF2D_RENDER
	void(*renderCallBack)(void*) = nullptr;
	void* obj;

	void RegisterRenderCallBack(void* newObj, void(*newRenderCallBack)(void*))
	{
		obj = newObj;
		renderCallBack = newRenderCallBack;
	}

	void RenderCallBack()
	{
		if (obj != nullptr && renderCallBack != nullptr)
		renderCallBack(obj);
	}
#endif

private:
	int width, height;
	Face* boundaryFace;

	std::vector<Face*> v_face;
	std::vector<Edge*> v_edge;
	std::vector<SymEdge*> v_symEdge;
	std::vector<Vertex*> v_vertex;
	std::vector<Constraint*> v_constraint;

	bool isMarking;
	unsigned int curMark;
};

#endif /* TRIANGULATION_HPP_ */
